1. Field of the Invention
The present invention relates to signal processing and, in particular, to computer-implemented processes and apparatus for efficient block comparisons in motion estimation systems.
2. Description of the Related Art
Motion estimation is commonly utilized by video encoders in signal processing techniques that compress successive frames of digital video data ("video frames"). When these video frames are to be transmitted via a communication medium of limited bandwidth, or are to be stored in a storage medium having limited storage capacity, it is often desirable to first compress the digital data which represents each frame, so as to reduce the amount of data that needs to be transmitted.
Motion estimation is one of the most computationally intense of the various techniques utilized to compress data. Motion estimation techniques exploit the temporal correlation that often exists between consecutive video frames, in which there is a tendency for objects or image features to move from one location to another on a display device from frame to frame.
For instance, frame 1 may contain an object, and frame 2 may contain a set of pixels corresponding to the same object spatially displaced by a few pixels from the location in frame 1. If frame 1 is transmitted to and received by a pixel processor or video processor (which performs any necessary decompression or other decoding), frame 2 may be transmitted without including the pixel data corresponding to the object. Instead, motion vectors (i.e. "pointers") are sent along with frame 2 (which may also be compressed using other techniques). These motion vectors may be utilized by the receiving video processor when decoding the received video frame 2 to reproduce the object from frame 1 at a new location within frame 2. Since such motion vectors can be represented with fewer bits than the pixels that comprise the object, fewer bits need to be transmitted (or stored) in order to recreate the object in frame 2.
The motion estimation procedure may be performed at the encoder level by comparing given regions or blocks within a current video frame to many regions or blocks within the previous video frame. The process of comparing a given block of one frame to a block of another frame is called "block matching." Blocks are matched by determining a "comparison measurement" between any given pair of blocks. A comparison measurement corresponds to some form of indication of a degree of "difference" between the two regions. If the comparison measurement is below a predetermined threshold, the blocks may be considered to be similar enough that a block match is indicated. If so, the block in the previous video frame may be utilized as described above by the video decoder to reproduce a duplicate block in the current video frame.
In performing such comparisons, a number of pixels from the previous video frame are accessed for each block of the current video frame that is subjected to motion estimation. In most general purpose video processing systems, the bit maps corresponding to the previous and current video frame pixels are stored in general purpose memory connected to the video processor through a bus. For each block matching procedure the video processor must access the memory many times, which may constitute a high amount of traffic on the bus and a high number of memory accesses. Because of the limited bandwidth of the bus by which the memory is accessed, these memory accesses can tie up use of the bus and memory and thus slow down overall operation of the video processing system.
To avoid this problem, the video processor performing the motion estimation step may contain, for example, a dedicated, special-purpose memory space to store the two video frames being compared so that there is less traffic on the bus. However, such a special-purpose memory space is often unavailable, unfeasible, or otherwise not desired because of the extra complexity of such a special-purpose memory. The special-purpose memory space may be too costly. Further, even a special purpose memory space may be accessed so often during block matching that the video processor may be slowed down.
What has been done in the past is to look at all the luminance values of the pixels within a block and to use a standard criterion (such as mean absolute error or mean square error) to accomplish accurate block matching. In their report of research done in connection with the Office of Naval Research under grant Number N00014-89-J1327, Andre Azccarin, et al, disclose a technique for using a pseudo-randomly selected subsampled set of pixel values in a target block to reduce the amount of computation needed for block matching. Their approach is useful in some circumstances, but does not take advantage of special identifying features of certain blocks.
It is accordingly an object of this invention to improve upon the techniques of the known art and to provide a method and apparatus that more efficiently uses available data to perform accurate and speedy block matching.
Further objects and advantages of this invention will become apparent from the Detailed Description of preferred embodiments which follows.